package edu.dayu.demo4;

/**
 * 计算这个字符串中有多少个回文子字符串。
 * 输入：s = "abc"
 * 输出：3
 * 解释：三个回文子串: "a", "b", "c"
 *
 * 思路：子字符串，那就是连续的。 所以问题变成了 怎么拿到 该字符的所有字串。
 *      求子字符串，先拿到 abc 然后 取 a ab abc 然后拿 bc 取 b bc 最后拿 c 取 c，双重循环
 *
 * 思路2： 中心扩散，选取一个 字符，然后往两边拓展，再选取 这个字符和下一个字符，来往两边拓展。
 */
public class 回文子字符串的个数 {
    public static void main(String[] args) {
         String s = "aaa";
        System.out.println(countSubstrings(s));
    }

    public static int countSubstrings(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            String str = s.substring(i);
            for (int i1 = 0; i1 < str.length(); i1++) {
                if(isPalindrome(str.substring(0,i1+1)))
                    count++;
            }
        }
        return count;
    }

    public static boolean isPalindrome(String s){
        int left = 0;
        int right = s.length()-1;
        while (left<=right){
            if (s.charAt(left)==s.charAt(right)){
                left++;
                right--;
            }else
                break;
        }
        return left>right;
    }

}
